Individual users commonly have multiple electronic devices. For example, an individual user may have a desktop computer, a laptop, a tablet, a cell phone, and a work computer. It is desirable to determine a set of devices that are associated with a particular user so that, when actions on those devices are tracked, the actions can be associated with a particular user profile and collectively used, for example, to identify and provide targeted marketing and content to the user. However, identifying a set of devices associated with a particular user is often difficult because users commonly have multiple devices, share devices with other users, borrow devices from one another, and use public-access devices. Existing techniques for automatically grouping devices for particular users attempt to make probabilistic determinations based on common IP addresses of devices. A technique that is not dependent on common IP addresses is desirable, because certain countries have privacy regulations barring the use of the full IP address.
Various clustering techniques are useful for grouping various types of data. However, clustering techniques have not been considered viable for grouping devices and users. For example, clustering techniques using certain algorithms such as k-Means algorithms to build computer network clusters require predetermined knowledge such as predetermined knowledge of the number of clusters and thus have been considered ill-suited for use in the context of clustering devices for users since the number of users is large, unknown, and changing over time. In addition, clustering techniques, such as RankClus and EvoNetClus, work with heterogeneous information networks and require the number of clusters to be estimated before running the algorithm. These techniques also assume that there are a very limited number of clusters, and therefore do not scale well in situations where the number of clusters is comparable with the number of nodes in the graph or otherwise involve a very large number of clusters.